# 迷宫： 我发现了迷宫有个重生的玩法，可以通过施加 `Weird_Substance` 来移动宝藏位置
# 那么我们可以在第一次不找宝藏， 而是扫描整个迷宫， 以便下次提前计算出路径，直接让无人机移动至宝藏

clear()
pet_the_piggy()
from utils import *

set_world_size(15)

l = get_world_size()

# 用于顺时针遍历的四个方向
DIRS = [North, East, South, West]
def get_next_pos(cur_pos, dir):
    x, y = cur_pos
    if dir == North:
        return (x, y + 1)
    elif dir == East:
        return (x + 1, y)
    elif dir == South:
        return (x, y - 1)
    else:
        return (x - 1, y)

def gamepos_to_arraypos(x,y):
    return (x*2,y*2)

def arraypos_to_gamepos(x,y):
    if x % 2 == 0 and y % 2 == 0:
        gx = x // 2
        gy = y // 2
        return (gx, gy)
    else:
        # 如果是无效的游戏坐标
        return None


substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)

def dfs_scan_map():
    map = [] # 二维数组 记录地图 0为道路 1为墙
    for _ in range(l*2 - 1):
        _line = []
        for _ in range(l*2 - 1):
            _line.append(1)
        map.append(_line)

    x0,y0 = get_pos() # 无人机起点
    array_x0,array_y0 = gamepos_to_arraypos(x0,y0)
    map[array_y0][array_x0] = 0
    
    stack = []
    visited = set()
    
    stack.append((x0,y0))
    visited.add((x0,y0))
    
    while (len(stack)>0):
        cur_pos = stack[-1]
        
        found_next_pos = False
        for dir in DIRS:
            next_pos = get_next_pos(cur_pos, dir)
            nx,ny = next_pos
            if can_move(dir) and next_pos != cur_pos and not next_pos in visited:
                # 移动
                move(dir)
                # 进栈
                stack.append(next_pos)
                # 标记访问
                visited.add(next_pos)
                # 将game坐标转换为array坐标, 并记录当前坐标为道路
                array_x,array_y = gamepos_to_arraypos(nx,ny)
                map[array_y][array_x] = 0
                # 将前后两个道路中间的墙壁也移除
                # 获取移动前的位置（栈中的倒数第二个位置）
                prev_x, prev_y = stack[-2]  # 移动前的位置
                # 转换为数组坐标
                prev_array_x, prev_array_y = gamepos_to_arraypos(prev_x, prev_y)
                # 计算墙壁位置（两点之间的中点）
                wall_array_x = (prev_array_x + array_x) // 2
                wall_array_y = (prev_array_y + array_y) // 2
                # 标记墙壁为通路
                map[wall_array_y][wall_array_x] = 0
                
                
                found_next_pos = True
                break
        if not found_next_pos:
            stack.pop()
            if len(stack) > 0:
                x,y = stack[-1]
                goto(l,x,y)
            else:
                break
    return map

def dfs_array_map(map):
    game_goal_x,game_goal_y = measure()
    array_goal_x,array_goal_y = gamepos_to_arraypos(game_goal_x,game_goal_y)
    map_len = len(map)
    stack = []
    visited = set()
    x0,y0 = get_pos()
    array_pos0 = gamepos_to_arraypos(x0,y0)
    stack.append(array_pos0)
    visited.add(array_pos0)

    while (len(stack)>0):
        cur_pos = stack[-1]
        if cur_pos[0] == array_goal_x and cur_pos[1] == array_goal_y:
            return stack
            
        found_next_pos = False
        for dir in DIRS:
            next_pos = get_next_pos(cur_pos, dir)
            if (0 <= next_pos[0] < map_len and 0 <= next_pos[1] < map_len) and map[next_pos[1]][next_pos[0]] == 0 and not next_pos in visited:
                stack.append(next_pos)
                visited.add(next_pos)
                found_next_pos = True
                break
        if not found_next_pos:
            stack.pop()
    return []

gen_maze_fullsize()
array_map = dfs_scan_map()

regen_times = 0
while 1:
    maze_path = dfs_array_map(array_map)

    for array_pos in maze_path:
        game_pos = arraypos_to_gamepos(array_pos[0],array_pos[1])
        if game_pos:
            goto(l,game_pos[0],game_pos[1])
    if regen_times >= 300: # 官方规则是300次后，宝藏就不会移动了
        harvest()
        break
    use_item(Items.Weird_Substance,substance)
 
